package binary_tree

import "container/list"

func IsCBT(root *TreeNode) bool {
	if root == nil {
		return true
	}
	queue := list.New()
	queue.PushFront(root)
	var meetLeaf bool
	for queue.Len() > 0 {
		n := queue.Remove(queue.Back()).(*TreeNode)
		if n.Left == nil && n.Right != nil { // 有左孩子无右孩子，不满足完全二叉树的条件，直接返回
			return false
		}
		if meetLeaf && (n.Left != nil || n.Right != nil) {
			// 如果已经有过叶子节点了，后续必须都为叶子节点，否则返回false
			return false
		}
		if n.Left != nil {
			queue.PushFront(n.Left)
		}
		if n.Left != nil {
			queue.PushFront(n.Right)
		}
		if n.Left == nil && n.Right == nil {
			// 遇到叶子节点，将遇到叶子节点标记为true
			meetLeaf = true
		}
	}
	return true
}
